package offer;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author Elephas
 * @Date 2022/3/18
 **/
public interface SubSets {
    List<List<Integer>> subsets(int[] nums);
}

class SubSetsImpl1 implements SubSets{

    @Override
    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        List<List<Integer>> ans = new ArrayList();

        if(n == 0){
            return ans;
        }else{
            boolean[] choose = new boolean[n];
            traceBack(choose, nums, n, ans);
            return ans;
        }
    }
    private void traceBack(boolean[] choose, int[] nums, int iter, List<List<Integer>> ans){
        if(iter > 0){
            choose[iter - 1] = false;
            traceBack(choose, nums, iter - 1, ans);
            choose[iter - 1] = true;
            traceBack(choose, nums, iter - 1, ans);
        }else{
            List<Integer> elem = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
                if(choose[i]) {
                    elem.add(nums[i]);
                }
            }
            ans.add(elem);
        }
    }
}